import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
public class Solution {
    //JZ55 二叉树的深度
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left =  TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }
    //JZ27 二叉树的镜像
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null){
            return null;
        }
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        swap(pRoot);
        return pRoot;
    }
    private void swap(TreeNode root){
        TreeNode tmp = root.left;
        root.left= root.right;
        root.right = tmp;
    }
    //判断两颗树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || p != null && q == null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    //JZ26 树的子结构
    private boolean sameTree(TreeNode root1,TreeNode root2){
        if(root1 == null && root2 != null){
            return false;
        }
        if(root2 == null){
            return true;
        }
        if(root1.val != root2.val){
            return false;
        }
        return sameTree(root1.left, root2.left) &&
                sameTree(root1.right, root2.right);
    }
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        //题中约定空树不为任何一颗树的子结构
        if(root2 == null){
            return false;
        }
        //一个为空，另一个不为空
        if(root1 == null && root2 != null){
            return false;
        }
        return sameTree(root1, root2)||
                HasSubtree(root1.left, root2)||
                HasSubtree(root1.right, root2);
    }
    //JZ79 判断是不是平衡二叉树
    //求树的高度
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left =  TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return left > right ? left + 1 : right + 1;
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        //为空说明到最后也没发现不平衡
        if(root == null){
            return true;
        }
        //每次递归都要保证高度差不能大于1，一旦大于一就没有必要往下走了
        if(Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1){
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
    //JZ28 对称的二叉树
    boolean isSymmetrical(TreeNode pRoot) {
        //空也是对称
        if(pRoot == null){
            return true;
        }
        //由于要比较左树和右树，题中所给的一个参数是不够的，所以另用一个函数
        return isSymmetricalChild(pRoot.left, pRoot.right);
    }
    boolean isSymmetricalChild(TreeNode leftTree, TreeNode rightTree){
        //有一方只要为空，而另一方不为空就不是对称
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null){
            return false;
        }
        //两个都为空
        if(leftTree == null && rightTree == null){
            return true;
        }
        //值不相同直接false
        if(leftTree.val != rightTree.val){
            return false;
        }
        //递归的去比较左树的左树和右树的右树是否相等
        //还有左树的右树和右树的左树是否相等
        return isSymmetricalChild(leftTree.left, rightTree.right) &&
                isSymmetricalChild(leftTree.right, rightTree.left);
    }
    //JZ32 从上往下打印二叉树
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> array = new ArrayList();
        if(root == null){
            return array;
        }
        //辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //队列只要不为空就弹出一个元素给cur
            TreeNode cur = queue.poll();
            //cur的值放入顺序表
            array.add(cur.val);
            //将cur所指向的结点的左右子树结点若不为空，则入队
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        return array;
    }
    //JZ68 二叉搜索树的最近公共祖先(非递归)
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //用两个顺序表分别记录p,q的路径
        ArrayList<Integer> arrayP = new ArrayList<>();
        ArrayList<Integer> arrayQ = new ArrayList<>();
        //记录一个顺序的值
        Set<Integer> set = new HashSet<>();
        //找p路径，根据二叉搜索树性质
        TreeNode cur = root;
        while(cur != null){
            set.add(cur.val);
            arrayP.add(cur.val);
            if(cur.val > p){
                cur = cur.left;
            }else if(cur.val < p){
                cur = cur.right;
            }else{
                break;
            }
        }
        //找q路径
        cur = root;
        while(cur != null){
            arrayQ.add(cur.val);
            if(cur.val > q){
                cur = cur.left;
            }else if(cur.val < q){
                cur = cur.right;
            }else{
                break;
            }
        }
        //从后向前找数据相同的
        int i = 0;
        for(i = arrayQ.size() - 1; i >= 0; i--){
            if(set.contains(arrayQ.get(i))){
                break;
            }
        }
        return arrayQ.get(i);
    }
    //JZ68 二叉搜索树的最近公共祖先(递归)
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //p和q都小于根节点
        if(p < root.val && q < root.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        //p和q的值都大于根结点
        if(p > root.val && q > root.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        //最后一种情况，一个大于一个小于或者等于
        return root.val;
    }
    //JZ36 二叉搜索树与双向链表
    TreeNode prev = null;
    public TreeNode createList(TreeNode root){
        if(root == null){
            return null;
        }
        createList(root.left);
        root.left = prev;
        if(prev != null){
            prev.right = root;
        }
        prev = root;
        createList(root.right);
        return root;//最后返回根结点
    }
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        TreeNode head = createList(pRootOfTree);
        //需要遍历到链表的头节点
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    //JZ86 在二叉树中找到两个节点的最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return func(root, o1, o2).val;
    }
    private TreeNode func(TreeNode root, int o1, int o2){
        if(root == null){
            return null;
        }
        //递归的过程若找到，就返回他
        if(root.val == o1 || root.val == o2){
            return root;
        }
        //分别去递归左右
        TreeNode left = func(root.left, o1, o2);
        TreeNode right = func(root.right, o1, o2);
        //分别在两边的情况，那么根节点就是公共祖先
        if(left != null && right != null){
            return root;
        }
        //只在一边找到
        else if(left != null){
            return left;
        }else{
            return right;
        }
    }
    //JZ86 在二叉树中找到两个节点的最近公共祖先（双栈法）
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return func(root, o1, o2).val;
    }
    private TreeNode func(TreeNode root, int p, int q){
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        //找路径
        fundPath(root, stackP, p);
        fundPath(root, stackQ, q);
        //比较两个路径谁长，长的一方出栈，直到持平
        while(stackP.size() > stackQ.size()){
            stackP.pop();
        }
        //比较两个路径谁长，长的一方出栈，直到持平
        while(stackP.size() < stackQ.size()){
            stackQ.pop();
        }
        //然后同时出栈,遇到相同的就停下，说明就是公共祖先
        while(stackP.peek() != stackQ.peek()){
            stackP.pop();
            stackQ.pop();
        }
        return stackP.peek();
    }
    private boolean fundPath(TreeNode root,Stack<TreeNode> stack, int val){
        if(root == null){
            return false;
        }
        //进来先压栈
        stack.push(root);
        if(root.val == val){
            return true;
        }
        //没找就递归下去
        boolean left = fundPath(root.left, stack, val);
        if(left){
            return true;
        }
        boolean right = fundPath(root.right, stack, val);
        if(right){
            return true;
        }
        //左右两边都没找到，说明此根节点不是路径，弹出即可
        stack.pop();
        return false;
    }
    //JZ33 二叉搜索树的后序遍历序列
    public boolean VerifySquenceOfBST(int [] array) {
        //要求空树不是二叉搜索树
        int len = array.length;
        if(len == 0){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        //用最大值先维护根节点
        int root = Integer.MAX_VALUE;
        //根->右->左
        for(int i = len - 1; i >= 0; i--){
            //已经确定目前数组中只含左子树，若左子树大于根节点，就不符合
            if(array[i] > root){
                return false;
            }
            //array[i]的值一旦小于前一项，说明进入左子树
            //在栈不为空的情况下弹出给root，为左子树的根结点
            while(!stack.isEmpty() && array[i] < stack.peek()){
                root = stack.pop();
            }
            //每个元素都要入栈一次
            stack.push(array[i]);
        }
        //没有违反规则
        return true;

    }
    //JZ77 按之字形顺序打印二叉树
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
        if(root == null){
            return retArray;
        }
        List<TreeNode> list = new LinkedList<>();
        //负责确定奇数还是偶数
        int count = 1;
        list.add(root);
        while(!list.isEmpty()){
            ArrayList<Integer> array = new ArrayList<>();
            //如果是奇数，每次从左往右入顺序表
            if(count % 2 != 0){
                for(int start = 0; start < list.size(); start++){
                    array.add(list.get(start).val);
                }
            }else{//偶数从右往左
                for(int end = list.size() - 1; end >= 0; end--){
                    array.add(list.get(end).val);
                }
            }
            //输入后入二维顺序表
            ArrayList<Integer> tmpArray = new ArrayList<>(array);
            retArray.add(tmpArray);
            //每次都删除零下标位置
            int tmp = 0;
            int row = list.size();
            while(!list.isEmpty() && tmp < row){
                TreeNode key = list.remove(0);
                //将key的左右结点放入链表
                if(key.left != null){
                    list.add(key.left);
                }
                if(key.right != null){
                    list.add(key.right);
                }
                tmp++;
            }
            //去下一行
            count++;
        }
        return retArray;
    }
    //JZ54 二叉搜索树的第k个节点（未优化）
    public int KthNode (TreeNode root, int k) {
        //对于二叉搜索树而言，中序遍历，就可以由小到大排出val值;
        ArrayList<Integer> array = new ArrayList<>();
        //得到顺序排列
        InitArray(root, array);
        //把不满足条件的排除
        if(root == null || array.size() < k || k == 0){
            return -1;
        }
        return array.get(k - 1);
    }
    //得到顺序排列
    private void InitArray(TreeNode root, ArrayList<Integer> array){
        if(root == null){
            return;
        }

        InitArray(root.left, array);
        array.add(root.val);
        InitArray(root.right, array);
    }
    //JZ54 二叉搜索树的第k个节点(优化)
    //记录递归次数
    private int count = 0;
    //记录第k小数字
    private int ret = -1;
    public int KthNode (TreeNode root, int k) {
        fundMin(root, k);
        if(ret != -1){
            return ret;
        }else{
            return -1;
        }
    }
    private void fundMin(TreeNode root, int k){
        if(root == null || count > k){
            return;
        }
        fundMin(root.left, k);
        count++;
        //遇到第k小就修改
        if(count == k){
            ret = root.val;
        }
        fundMin(root.right, k);
    }
    //JZ82 二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        //进入叶子结点
        if(root.left == null && root.right == null && sum - root.val == 0){
            return true;
        }
        //不满足以上两点，才继续递归
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
    //JZ34 二叉树中和为某一值的路径(二)
    private ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
    private ArrayList<Integer> array = new ArrayList<>();
    //寻找正确路径
    private void fundPath(TreeNode root, int sum){
        if(root == null){
            return;
        }
        array.add(root.val);
        //路径到了叶子结点
        if(root.left == null && root.right == null && sum - root.val == 0){
            //若进来了，说明此路径正确，加入到二维顺序表中
            retArray.add(new ArrayList<>(array));
        }
        //递归左右树
        fundPath(root.left, sum - root.val);
        fundPath(root.right, sum - root.val);
        //到了这里，说明不是正确路径，删除上一个元素
        array.remove(array.size() - 1);
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        fundPath(root, expectNumber);
        return retArray;
    }
    //JZ84 二叉树中和为某一值的路径(三)
    //计数器
    private int count = 0;
    public int FindPath (TreeNode root, int sum) {
        if(root == null){
            return count;
        }
        //每一个结点都可以作为根结点开始
        fundPath(root, sum);
        FindPath(root.left, sum);
        FindPath(root.right, sum);
        return count;
    }
    public void fundPath(TreeNode root, int sum){
        if(root == null){
            return;
        }
        //满足则计数器就加一
        if(sum - root.val == 0){
            count++;
        }
        //递归左右结点
        fundPath(root.left, sum - root.val);
        fundPath(root.right, sum - root.val);
    }
    //JZ78 把二叉树打印成多行
    ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        //此题说白了就是层序遍历，并记录每一层数据
        ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
        //若为空，直接返回
        if(root == null){
            return retArray;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        //先将根节点入队
        queue.offer(root);
        while(!queue.isEmpty()){
            ArrayList<Integer> array = new ArrayList<>();
            //记录每层的长度
            int len = queue.size();
            //有几个结点，就让每个结点的子结点放入队列
            for(int i = 0; i < len; i++){
                TreeNode tmp = queue.poll();
                //放入顺序表
                array.add(tmp.val);
                //若子节点不是空指针则将子节点放入队列
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
            }
            //将每一层放入二维顺序表
            retArray.add(array);
        }
        return retArray;
    }
    //JZ37 序列化二叉树
    String Serialize(TreeNode root) {
        //层序遍历
        StringBuilder stringBuilder = new StringBuilder();
        //防止为空
        if(root == null){
            return stringBuilder.toString();
        }
        //用队列辅助序列化
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            if(tmp != null){
                stringBuilder.append(tmp.val);
                stringBuilder.append(",");
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }else{
                stringBuilder.append("Null,");
            }
        }
        return stringBuilder.toString();
    }
    TreeNode Deserialize(String str) {
        if(str==null||str.length()==0){
            return null;
        }
        String[] sb=str.split("\\,");
        TreeNode root=new TreeNode(Integer.parseInt(sb[0]));
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int i=1;    //字符串数组下标
        while(!queue.isEmpty()){
            TreeNode temp=queue.poll();
            if(!sb[i].equals("Null")){
                temp.left=new TreeNode(Integer.parseInt(sb[i]));
                queue.offer(temp.left);
            }
            i++;
            if(!sb[i].equals("Null")){
                temp.right=new TreeNode(Integer.parseInt(sb[i]));
                queue.offer(temp.right);
            }
            i++;
        }
        return root;
    }
}
